//
//  BinaryTree 
//
//  Created by zhuoooo on 2022/12/7.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//  二叉树算法

#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_SIZE 100    //二叉树的最大节点数
#define OK 1
#define ERROR -1

//二叉树的定义
typedef char ElemType;
typedef int Status;
typedef struct BTNode
{
    ElemType data;                   //二叉树的值
    struct BTNode *Lchild, *Rchild;  //二叉树的左右孩子
    
}BTNode;

Status Init_BTNode(BTNode *T);//创建一个空的二叉树
Status CreateBiTree(BTNode *T);//递归创建一棵二叉树，输入按二叉树的先序输入
void DestroyBiTree(BTNode *T);//递归销毁一棵二叉树
Status DepthofBiTree(BTNode *T);//递归求二叉树的深度
Status LeafcountOfBiTree(BTNode *T);//递归求二叉树的子节点个数
void PreOrdertraverse(BTNode *T);//先序遍历二叉树
void InOrderTraverse(BTNode *T);//中序遍历二叉树
void PostOrderTraverse(BTNode *T);//后序遍历二叉树

int main(int argc, const char * argv[]) {
    // insert code here...
    int num, res = 0;
    BTNode T;
    printf("1.初始化一个空的二叉树\n2.初始化二叉树\n3.求二叉树的深度\n4.求二叉树的子节点个数\n5.先序遍历二叉树\n6.中序遍历二叉树\n7.后序遍历二叉树\n8.销毁二叉树\n9.退出\n");
    
    while (1) {
        printf("请输入您要执行的操作：");
        scanf("%d", &num);
        if (num == 1) {
            res = Init_BTNode(&T);
            if (res == 1) {
                printf("初始化成功！\n");
            }
        }
        else if (num == 2) {
            res = CreateBiTree(&T);
            if (res == 1) {
                printf("二叉树赋值成功");
            }
            
        }
        else if (num == 3){
            res = DepthofBiTree(&T);
            printf("二叉树的深度为%d\n",res);
        }
        else if (num == 4){
            res = LeafcountOfBiTree(&T);
            printf("二叉树的子节点数为%d\n", res);
        }
        else if (num == 5){
            PreOrdertraverse(&T);
        }else if(num == 6){
            InOrderTraverse(&T);
        }else if(num == 7){
            PostOrderTraverse(&T);
        }else if (num == 8){
            DepthofBiTree(&T);
        }else{
            break;
        }
    }
    
    return 0;
}
Status Init_BTNode(BTNode *T)//创建一个空的二叉树
{
    T->Lchild = NULL;
    T->Rchild = NULL;
    T->data = '\0';
    
    return OK;
}
Status CreateBiTree(BTNode *T)//递归创建一棵二叉树，输入按二叉树的先序输入
{
    ElemType ch;
    printf("当输入0字符后二叉树赋值结束！\n");
    fflush(stdin);
    scanf("%c", &ch);
    printf("zifu:%c", ch);
    if (ch == '0') {
        return OK;
    }else{
        if(ch == '*')
            T = NULL;
        else
        {
            T = (BTNode *)malloc(sizeof(BTNode));
            T->data = ch;
            CreateBiTree(T->Lchild);
        }
    }
    return OK;
    
}

void DestroyBiTree(BTNode *T)//递归销毁一棵二叉树
{
    if (T) {
        DestroyBiTree(T->Lchild);
        DestroyBiTree(T->Rchild);
        free(T);
        T = NULL;
    }
}
Status DepthofBiTree(BTNode *T)//递归求树的深度
{
    int ldepth;
    int rdepth;
    
    if (!T) {
        return ERROR;
    }else{
        ldepth = DepthofBiTree(T->Lchild);
        rdepth = DepthofBiTree(T->Rchild);
    }
    if (ldepth > rdepth) {
        return ldepth+1;
    }else{
        return rdepth+1;
    }
    
}
Status LeafcountOfBiTree(BTNode *T)//递归求二叉树的子节点个数
{
    if (!T) {
        return ERROR;
    }
    else if (T->Lchild == NULL && T->Rchild == NULL){
        return OK;
    }
    else{
        return LeafcountOfBiTree(T->Lchild) + LeafcountOfBiTree(T->Rchild);
    }
}
void PreOrdertraverse(BTNode *T)//先序遍历二叉树
{
    if (!T) {
        printf("二叉树为空!\n");
    }
    else{
        printf("%c", T->data);
        PreOrdertraverse(T->Lchild);
        PreOrdertraverse(T->Rchild);
    }
}
void InOrderTraverse(BTNode *T)//中序遍历二叉树
{
    if (!T) {
        printf("二叉树为空!\n");
    }else{
        InOrderTraverse(T->Lchild);
        printf("%c", T->data);
        InOrderTraverse(T->Rchild);
    }
}
void PostOrderTraverse(BTNode *T)//后序遍历二叉树
{
    if (!T) {
        printf("二叉树为空!\n");
    }else{
        PostOrderTraverse(T->Lchild);
        PostOrderTraverse(T->Rchild);
        printf("%c", T->data);
    }
}
